/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 17655
 * Date: 2024-12-24
 * Time: 11:59
 */
public class test2 {
    /*
    LCR 170  交易逆序对的总数
     */
    int[] tmp;
    public int reversePairs(int[] nums) {
        int n=nums.length;
        tmp = new int[n];
        return mergeSort(nums,0,n-1);
    }

    public int mergeSort(int[] nums,int left,int right){
        if(left>=right){
            return 0;
        }

        int ret = 0;
        int mid = (right-left)/2 +left;
        // [left,mid] [mid+1,right]

        ret += mergeSort(nums,left,mid);
        ret += mergeSort(nums,mid+1,right);

        int cur1 = left;
        int cur2 = mid+1;
        int i=0;
        while(cur1<=mid && cur2<=right){
            if(nums[cur1]<=nums[cur2]){
                tmp[i++] = nums[cur1++];
            }else{
                ret +=mid-cur1+1;
                tmp[i++] = nums[cur2++];
            }
        }

        // 排序
        while(cur1<=mid){
            tmp[i++] = nums[cur1++];
        }
        while(cur2<=right){
            tmp[i++] = nums[cur2++];
        }
        for(int j=left;j<=right;j++){
            nums[j] = tmp[j-left];
        }
        return ret;
    }
}
